package com.tang.algorithm.dynamicProgramming;

/**
 * @author tlm
 * @Description
 * @date 2020/6/22 21:28 下午
 */
public class LeetCode338 {
    public static void main(String[] args) {
        int[] res = countBits(15);
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }
    }

    // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    // 0 1 1 2 1 2 2 3 1 2 2  3  2  3  3  4
    public static int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}
